package middle;

import java.util.ArrayList;
import java.util.List;
import util.PrintUtils;

public class Solution_93 {
    private List<String> list;
    private final StringBuilder builder = new StringBuilder();
    private final int[] indexes = {-1, -1, -1, -1};
    public List<String> restoreIpAddresses(String s) {
        list = new ArrayList<>();
        char[] chars = s.toCharArray();
        dps(chars, 0, 4);
        return list;
    }

    private void dps(char[] chars, int begin, int count) {
        if (count == 0) {
            if (begin == chars.length) {
                builder.delete(0, builder.length());
                for (int index : indexes) {
                    builder.append(index).append('.');
                }
                list.add(builder.substring(0, builder.length() - 1));
            }
            return;
        }
        int num = 0;
        for (int i = begin; i < chars.length; i++) {
            if (chars[begin] == '0' && i > begin) {
                break;
            }
            num = num * 10 + (chars[i] - '0');
            if (num >= 256) {
                break;
            }
            indexes[indexes.length - count] = num;
            dps(chars, i + 1, count - 1);
        }
    }

    public static void main(String[] args) {
        Solution_93 model = new Solution_93();
        System.out.println(model.restoreIpAddresses("25525511135"));;
        System.out.println(model.restoreIpAddresses("0000"));;
        System.out.println(model.restoreIpAddresses("101023"));;
    }
}
